#define _CRT_SECURE_NO_WARNINGS
#include<iostream>
#include<vector>
#include<string>
#include<functional>
#include<numeric>
#include<unordered_set>
using namespace std;

//bool containsCycle(vector<vector<char>>& grid) {
//	int dx[4] = { 0,0,1,-1 }, dy[4] = { 1,-1,0,0 };
//	int m = grid.size(), n = grid[0].size();
//	vector<vector<bool>> visited(m, vector<bool>(n, false));
//	int starti, startj;
//	function<int(int, int)> dfs = [&](int i, int j)->int
//	{
//		int path = 1;
//		for (int k = 0; k < 4; k++)
//		{
//			int x = i + dx[k], y = j + dy[k];
//			if (x >= 0 && x < m && y >= 0 && y < n && visited[x][y] == false
//				&& grid[x][y] == grid[starti][startj])
//			{
//				visited[x][y] = true;
//				path = dfs(x, y) + 1;
//			}
//		}
//		return path;
//	};
//	for (int i = 0; i < m; i++)
//	{
//		for (int j = 0; j < n; j++)
//		{
//			if (visited[i][j] == false)
//			{
//				starti = i;
//				startj = j;
//				visited[i][j] = true;
//				if (dfs(i, j) >= 4)
//				{
//					int cnt = 0;
//					for (int k = 0; k < 4; k++)
//					{
//						int x = i + dx[k], y = j + dy[k];
//						if (x >= 0 && x < m && y >= 0 && y < n && visited[x][y] == true
//							&& grid[x][y] == grid[starti][startj])
//							cnt++;
//					}
//					if (cnt >= 2)
//						return true;
//				}
//			}
//		}
//	}
//	return false;
//}
class Djset
{
public:
	vector<int> parent;
	vector<int> count;
	Djset(int n)
	{
		parent.resize(n);
		iota(parent.begin(), parent.end(), 0);
		count.resize(n, 0);
	}
	int find(int x)
	{
		if (x != parent[x])
			parent[x] = find(parent[x]);
		return parent[x];
	}
	void merge(int x, int y)
	{
		int fx = find(x), fy = find(y);
		if (fx == fy)
			return;
		parent[fy] = fx;
		count[fx]++;
	}
};
bool containsCycle(vector<vector<char>>& grid) {
	int m = grid.size(), n = grid[0].size();
	Djset ds(m * n);
	for (int i = 0; i < m; i++)
	{
		for (int j = 0; j < n; j++)
		{
			int x = i * n + j;
			if (i > 0 && grid[i][j] == grid[i - 1][j])
			{
				int y = (i - 1) * n + j;
				if (ds.find(x) != ds.find(y))
					ds.merge(x, y);
				else
					return true;
			}
			if (j > 0 && grid[i][j] == grid[i][j - 1])
			{
				int z = i * n + j - 1;
				if (ds.find(x) != ds.find(z))
					ds.merge(x, z);
				else
					return true;
			}
		}
	}
	return false;
}

int largestIsland(vector<vector<int>>& grid) {
	int m = grid.size(), n = grid[0].size();
	int dx[4] = { 0,0,1,-1 }, dy[4] = { 1,-1,0,0 };
	Djset ds(m * n);
	for (int i = 0; i < m; i++)
	{
		for (int j = 0; j < n; j++)
		{
			int x = i * n + j;
			if (grid[i][j] == 1)
				ds.count[i * n + j] = 1;
			if (i > 0 && grid[i][j] == 1 && grid[i][j] == grid[i - 1][j])
			{
				int y = (i - 1) * n + j;
				ds.merge(x, y);
			}
			if (j > 0 && grid[i][j] == 1 && grid[i][j] == grid[i][j - 1])
			{
				int z = i * n + j - 1;
				ds.merge(x, z);
			}
		}
	}
	int ret = 0;
	bool flag = false;
	for (int i = 0; i < m; i++)
	{
		for (int j = 0; j < n; j++)
		{
			if (grid[i][j] == 0)
			{
				flag = true;
				int path = 1;
				unordered_set<int> hash;
				for (int k = 0; k < 4; k++)
				{
					int x = i + dx[k], y = j + dy[k];
					if (x >= 0 && x < m && y >= 0 && y < n && !hash.count(ds.find(x * n + y)))
					{
						hash.insert(ds.find(x * n + y));
						path += ds.count[ds.find(x * n + y)];
					}
				}
				ret = max(ret, path);
			}
		}
	}
	if (flag == false)
		return ds.count[ds.find(0)];
	else
		return ret;
}
int main()
{
	vector<vector<int>> grid = { {1,0},{0,1} };
	largestIsland(grid);
	return 0;
}